from collections import Counter, deque


class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:
        rec = Counter(word)
        a = deque(sorted(rec.items(), key=lambda x: x[1]))
        ans = 0
        while a and a[0][1] - a[-1][1] > k:
            if a[0][1] - a[-1][1] - k > a[-1][1]:
                ans += a[-1][1]
                a.pop()
            elif a[0][1] - a[-1][1] - k == a[-1][1]:
                ans += a[-1][1]
                a.popleft()
                a.pop()
        while a and a[0][1] - a[-1][1] > k:
            ans += a[0][1] - a[-1][1] - k
            a.popleft()
        return ans
